Neural Information Processing Systems http://nips.cc/

The Weighted First-Order Model Counting Problem (WFOMC) asks to compute the weighted sum of models of a given first-order logic sentence over a given domain. Conditioning WFOMC on evidence -- fixing the truth values of a set of ground literals -- has been shown impossible in time polynomial in the domain size (unless $\mathsf{\#P \subseteq FP}$) even for fragments of logic that are otherwise tractable for WFOMC without evidence. In this work, we address the barrier by restricting the binary evidence to the case where the underlying Gaifman graph has bounded treewidth. We present a polynomial-time algorithm in the domain size for computing WFOMC for the two-variable fragments $\text{FO}^2$ and $\text{C}^2$ conditioned on such binary evidence. Furthermore, we show the applicability of our algorithm in combinatorial problems by solving the stable seating arrangement problem on bounded-treewidth graphs of bounded degree, which was an open problem. We also conducted experiments to show the scalability of our algorithm compared to the existing model counting solvers.

First provide a summary of the paper, and then address the following criteria: Quality, clarity, originality and significance. This paper introduces two new lifted inference rules for MAP. They apply when there are -for the MPA task-redundant logical variables, and when formulas are always true when entire relations are set to true/false. The definition of domain independence should be made more precise. In its current form, there is a problem.

We investigate the problem of learning an unknown probability distribution over a discrete population from random samples. Our goal is to design efficient algorithms that simultaneously achieve low error in total variation norm while guaranteeing Differential Privacy to the individuals of the population. We describe a general approach that yields near sample-optimal and computationally efficient differentially private estimators for a wide range of well-studied and natural distribution families. Our theoretical results show that for a wide variety of structured distributions there exist private estimation algorithms that are nearly as efficient--both in terms of sample size and running time--as their non-private counterparts. We complement our theoretical guarantees with an experimental evaluation. Our experiments illustrate the speed and accuracy of our private estimators on both synthetic mixture models and a large public data set.

We present a deep learning emulator for stochastic and chaotic spatio-temporal systems, explicitly conditioned on the parameter values of the underlying partial differential equations (PDEs). Our approach involves pre-training the model on a single parameter domain, followed by fine-tuning on a smaller, yet diverse dataset, enabling generalisation across a broad range of parameter values. By incorporating local attention mechanisms, the network is capable of handling varying domain sizes and resolutions. This enables computationally efficient pre-training on smaller domains while requiring only a small additional dataset to learn how to generalise to larger domain sizes. We demonstrate the model's capabilities on the chaotic Kuramoto-Sivashinsky equation and stochastically-forced beta-plane turbulence, showcasing its ability to capture phenomena at interpolated parameter values. The emulator provides significant computational speed-ups over conventional numerical integration, facilitating efficient exploration of parameter space, while a probabilistic variant of the emulator provides uncertainty quantification, allowing for the statistical study of rare events.

We consider four types of benchmarks in our experiments, i.e., random COPs, scale-free networks, Therefore, to be fair and practical, we do not consider existing DNN-based BP variants. We compare our DABP with the following state-of-the-art COP solvers: (1) DBP with a damping factor of 0.9 and its splitting constraint factor graph version (DBP-SCFG) with a splitting ratio of 0.95 [ However, it can be extremely tedious and time-consuming to tune the damping factor. Figure 9: Convergence rates under different iteration limits ( | X | = 100) 4 size (i.e., 5) and the constraint functions are highly structured, which allows effective pruning and It also can be concluded that our DABP converges much faster than DBP and DBP-SCFG. To demonstrate the necessity of heterogeneous hyperparameters of Eq. (6), we conduct extensive Figure 1-12 present the results on solution quality. Table 1 presents the GPU memory footprint of our DABP .

Decision Diagram (AOMDD) which represents all its optimal solutions.

The Weighted First-Order Model Counting Problem (WFOMC) asks to compute the weighted sum of models of a given first-order logic sentence over a given domain. The boundary between fragments for which WFOMC can be computed in polynomial time relative to the domain size lies between the two-variable fragment ($\text{FO}^2$) and the three-variable fragment ($\text{FO}^3$). It is known that WFOMC for \FOthree{} is $\mathsf{\#P_1}$-hard while polynomial-time algorithms exist for computing WFOMC for $\text{FO}^2$ and $\text{C}^2$, possibly extended by certain axioms such as the linear order axiom, the acyclicity axiom, and the connectedness axiom. All existing research has concentrated on extending the fragment with axioms on a single distinguished relation, leaving a gap in understanding the complexity boundary of axioms on multiple relations. In this study, we explore the extension of the two-variable fragment by axioms on two relations, presenting both negative and positive results. We show that WFOMC for $\text{FO}^2$ with two linear order relations and $\text{FO}^2$ with two acyclic relations are $\mathsf{\#P_1}$-hard. Conversely, we provide an algorithm in time polynomial in the domain size for WFOMC of $\text{C}^2$ with a linear order relation, its successor relation and another successor relation.

"The paper presents novel theoretical results that are highly relevant for the machine learning community" (Reviewer The results are impressive, non-trivial and interesting" (Reviewer 4). The remainder of this response mostly addresses suggestions and questions raised by Reviewers 1 and 3. Both Reviewers 1 and 3 ask us to elaborate on the differences between [JO19] and this paper. By contrast, this paper utilizes the distribution's structure, or even rough proximity to a structure, to identify a much Reviewer 1 writes, requires a "non-trivial" combination of VC theory and the filtering framework, allows us to remove Regarding Reviewer 1's specific question whether the technique also applies when the distributions underlying genuine We will add a similar explanation to the final version. This relation was explained in [JO19]. To enhance the reader's understanding of the context, in the final version of Please note that Section 3 of the paper starts by stating that "The current results extend several long lines of For the reader's benefit we will follow the reviewer's advice and We fully sympathize with the reviewer's desire to see more hard proofs in the We also note that Reviewer 4's response to question 2 seems We will try to accommodate Reviewer 1's request by including as much information Finally, Reviewer 3 asks about the time complexity of the paper's two efficient algorithms: learning piecewise Both algorithms have very reasonable complexities.